Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach
Identifieur interne : 000C34 ( Main/Exploration ); précédent : 000C33; suivant : 000C35Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach
Auteurs : Christophe Costa Florêncio [Belgique] ; Henning Fernau [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2010.
Abstract
Abstract: Kanazawa ([8]) has studied the learnability of several parameterized families of classes of categorial grammars. These classes were shown to be learnable from text, in the technical sense of identifiability in the limit from positive data. They are defined in terms of bounds on certain parameters of the grammars. Intuitively, these bounds correspond to restrictions on linguistic aspects such as the amount of lexical ambiguity of the grammar. The time complexity of learning these classes has been studied by Costa Florêncio ([4]). It was shown that for most of these classes, selecting a grammar from the class that is consistent with the data is NP-hard. In this paper existing complexity results are sharpened by demonstrating W[2]-hardness. Additional parameters allowing FPT-results are also studied, and it is shown that if these parameters are fixed, these problems become computable in polynomial time. As far as the authors are aware, this is the first such result for learning problems.
Url:
DOI: 10.1007/978-3-642-13089-2_17
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001A92
- to stream Istex, to step Curation: 001975
- to stream Istex, to step Checkpoint: 000313
- to stream Main, to step Merge: 000C88
- to stream Main, to step Curation: 000C34
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach</title><author><name sortKey="Costa Florencio, Christophe" sort="Costa Florencio, Christophe" uniqKey="Costa Florencio C" first="Christophe" last="Costa Florêncio">Christophe Costa Florêncio</name></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:05B669A8A52C0DD3027866D0B0C80AA55FBB31F7</idno><date when="2010" year="2010">2010</date><idno type="doi">10.1007/978-3-642-13089-2_17</idno><idno type="url">https://api.istex.fr/document/05B669A8A52C0DD3027866D0B0C80AA55FBB31F7/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001A92</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001A92</idno><idno type="wicri:Area/Istex/Curation">001975</idno><idno type="wicri:Area/Istex/Checkpoint">000313</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000313</idno><idno type="wicri:doubleKey">0302-9743:2010:Costa Florencio C:finding:consistent:categorial</idno><idno type="wicri:Area/Main/Merge">000C88</idno><idno type="wicri:Area/Main/Curation">000C34</idno><idno type="wicri:Area/Main/Exploration">000C34</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach</title><author><name sortKey="Costa Florencio, Christophe" sort="Costa Florencio, Christophe" uniqKey="Costa Florencio C" first="Christophe" last="Costa Florêncio">Christophe Costa Florêncio</name><affiliation wicri:level="1"><country xml:lang="fr">Belgique</country><wicri:regionArea>Department of Computer Science, K.U. Leuven, Leuven</wicri:regionArea><wicri:noRegion>Leuven</wicri:noRegion></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV—Abteilung Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2010</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">05B669A8A52C0DD3027866D0B0C80AA55FBB31F7</idno><idno type="DOI">10.1007/978-3-642-13089-2_17</idno><idno type="ChapterID">17</idno><idno type="ChapterID">Chap17</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Kanazawa ([8]) has studied the learnability of several parameterized families of classes of categorial grammars. These classes were shown to be learnable from text, in the technical sense of identifiability in the limit from positive data. They are defined in terms of bounds on certain parameters of the grammars. Intuitively, these bounds correspond to restrictions on linguistic aspects such as the amount of lexical ambiguity of the grammar. The time complexity of learning these classes has been studied by Costa Florêncio ([4]). It was shown that for most of these classes, selecting a grammar from the class that is consistent with the data is NP-hard. In this paper existing complexity results are sharpened by demonstrating W[2]-hardness. Additional parameters allowing FPT-results are also studied, and it is shown that if these parameters are fixed, these problems become computable in polynomial time. As far as the authors are aware, this is the first such result for learning problems.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>Belgique</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="Belgique"><noRegion><name sortKey="Costa Florencio, Christophe" sort="Costa Florencio, Christophe" uniqKey="Costa Florencio C" first="Christophe" last="Costa Florêncio">Christophe Costa Florêncio</name></noRegion></country><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name></region><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C34 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000C34 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:05B669A8A52C0DD3027866D0B0C80AA55FBB31F7
|texte= Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach
}}
| This area was generated with Dilib version V0.6.31. |  |